package theeg.DependencyAnalysis.Core.Algorithms.SubstringDetection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GeneralizedSuffixTree {

    public static final char Delimiter = '\ufffe';

    private final char[][] _texts;
    private final int[] _offsets;
    private final SuffixTree _suffixTree;

    public GeneralizedSuffixTree(char[][] texts) {
        char[] terminators = getDefaultTerminators(texts.length);
        _texts = texts;
        _offsets = new int[texts.length];
        int currentOffset = 0;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < texts.length; i++) {
            stringBuilder.append(texts[i]);
            stringBuilder.append(terminators[i]);
            _offsets[i] = currentOffset;
            currentOffset += texts[i].length + 1;
        }
        char[] generalized = stringBuilder.toString().toCharArray();
        _suffixTree = new SuffixTree(generalized);
        fixSpanSuffixes(_suffixTree.getRootNode());
    }

    private void fixSpanSuffixes(Node node) {
        for (Edge edge : node.getEdges()) {
            for (int i = 0; i < _texts.length; i++) {
                int length = getGeneralizedSubstringLength(i);
                if ((edge.beginIndex <= length)
                        && (edge.endIndex > length)) {
                    edge.endIndex = length;
                }
            }
            fixSpanSuffixes(edge.endNode);
        }
    }

    private int getGeneralizedSubstringLength(int n) {
        return _offsets[n] + _texts[n].length;
    }

    public CommonSubstring findLongestCommonSubstring() {
        int[] beginIndexes = new int[_texts.length];
        int[] endIndexes = new int[_texts.length];
        InitBeginEndIndexes(beginIndexes, endIndexes);

        HashMap<Node, CommonSubstringStatus> statuses = new HashMap();
        getLcsNodeStatus(_suffixTree.getRootNode(), 0, statuses);

        CommonSubstring commonSubstring = findLongestCommonSubstring(beginIndexes, endIndexes, statuses);
        statuses.clear();

        return commonSubstring;
    }

    private void InitBeginEndIndexes(int[] beginIndexes, int[] endIndexes) {
        beginIndexes[0] = 0;
        endIndexes[0] = _texts[0].length;

        for (int i = 1; i < _texts.length; i++) {
            beginIndexes[i] = endIndexes[i - 1] + 1;
            endIndexes[i] = beginIndexes[i] + _texts[i].length;
        }
    }

    public static char[] getDefaultTerminators(int length) {
        char[] terminators = new char[length];
        for (int i = 0; i < length; i++) {
            terminators[i] = (char) (1000 + i % 50000);
        }
        return terminators;
    }

    public int[] incIndexes(int[] indexes) {
        for (int i = 0; i < _texts.length; i++) {
            indexes[i]++;
        }
        return indexes;
    }

    private CommonSubstring findLongestCommonSubstring(int[] beginIndexes, int[] endIndexes, HashMap<Node, CommonSubstringStatus> statuses) {
        int max = 0;
        int[] foundBeginIndexes = null;

        for (CommonSubstringStatus status : statuses.values()) {
            if ((status.height > 0) && (status.isInAllStrings()) && (max <= status.height)) {
                Node node = status.node;
                int[] workingBeginIndexes = initFoundBeginIndexes();

                updateFoundBeginIndexes(new UpdateFoundBeginIndexesParams(beginIndexes, endIndexes, node, status.height, statuses, workingBeginIndexes));

                if (verifyFoundBeginIndexes(workingBeginIndexes)) {
                    foundBeginIndexes = workingBeginIndexes;
                    max = status.height;
                }
            }
        }

        if (foundBeginIndexes == null) {
            return null;
        }
        for (int i = 0; i < foundBeginIndexes.length; i++) {
            foundBeginIndexes[i] -= _offsets[i];
        }
        CommonSubstring result = new CommonSubstring();
        result.beginIndices = foundBeginIndexes;
        result.length = max;
        return result;
    }

    private int[] initFoundBeginIndexes() {
        int[] beginIndexes = new int[_texts.length];
        for (int i = 0; i < _texts.length; i++) {
            beginIndexes[i] = Integer.MAX_VALUE;
        }
        return beginIndexes;
    }

    class UpdateFoundBeginIndexesParams {

        public final int[] beginIndexes;
        public final int[] endIndexes;
        private final Node node;
        private final int height;
        private final HashMap<Node, CommonSubstringStatus> statuses;
        private final int[] foundBeginIndexes;

        public UpdateFoundBeginIndexesParams(int[] beginIndexes,
                int[] endIndexes,
                Node node,
                int height,
                HashMap<Node, CommonSubstringStatus> statuses,
                int[] foundBeginIndexes) {
            this.beginIndexes = beginIndexes;
            this.endIndexes = endIndexes;
            this.node = node;
            this.height = height;
            this.statuses = statuses;
            this.foundBeginIndexes = foundBeginIndexes;
        }
    }

    private void updateFoundBeginIndexes(UpdateFoundBeginIndexesParams parameter) {
        for (Edge edge : parameter.node.getEdges()) {
            CommonSubstringStatus nodeStatus = parameter.statuses.containsKey(edge.endNode) ? parameter.statuses.get(edge.endNode) : null;
            if ((nodeStatus != null) && nodeStatus.isInAllStrings()) {
                updateFoundBeginIndexes(new UpdateFoundBeginIndexesParams(parameter.beginIndexes, parameter.endIndexes, edge.endNode, parameter.height + getEdgeHeight(edge), parameter.statuses, parameter.foundBeginIndexes));
            } else {
                int stringNumber = getEdgeStringNumber(edge);
                int beginIndex = edge.beginIndex - parameter.height;

                if ((beginIndex < parameter.endIndexes[stringNumber])
                        && (beginIndex >= parameter.beginIndexes[stringNumber])
                        && (parameter.foundBeginIndexes[stringNumber] > beginIndex)) {

                    parameter.foundBeginIndexes[stringNumber] = beginIndex;
                }
            }
        }
    }

    private boolean verifyFoundBeginIndexes(int[] beginIndexes) {
        for (int i = 0; i < _texts.length; i++) {
            if (beginIndexes[i] < 0) {
                return false;
            }
        }
        return true;
    }

    private int getEdgeStringNumber(Edge edge) {
        for (int i = 0; i < _texts.length; i++) {
            if (edge.endIndex <= getGeneralizedSubstringLength(i)) {
                return i;
            }
        }
        return -1;
    }

    private int getEdgeHeight(Edge edge) {
        return edge.endIndex - edge.beginIndex;
    }

    private int getEdgeHeightForNodeStatus(Edge edge) {
        int result = getEdgeHeight(edge);

        int stringNumber = getEdgeStringNumber(edge);
        if (edge.endIndex != getGeneralizedSubstringLength(stringNumber)) {
            result += 1;
        }
        return result;
    }

    public List<CommonSubstring> findCommonSubstrings(int minimalLength) {
        HashMap<Node, CommonSubstringStatus> statuses = new HashMap();
        getLcsNodeStatus(_suffixTree.getRootNode(), 0, statuses);
        List<CommonSubstringStatus> duplicates = new ArrayList();
        for (CommonSubstringStatus x : statuses.values()) {
            if (x.height >= minimalLength && x.isInAtLeastTwoStrings()) {
                duplicates.add(x);
            }
        }

        List<CommonSubstring> substrings = removeInclusiveSubstrings(duplicates);
        for (CommonSubstring substring : substrings) {
            for (int i = 0; i < substring.textIndices.length; i++) {
                substring.beginIndices[i] -= _offsets[substring.textIndices[i]];
            }
        }
        return substrings;
    }

    private List<CommonSubstring> removeInclusiveSubstrings(Collection<CommonSubstringStatus> duplicates) {
        List<CommonSubstring> commonSubstrings = new ArrayList();
        Map<String, CommonSubstring> longestSubstrings = new HashMap();
        for (CommonSubstringStatus status : duplicates) {
            Edge[] edges = status.node.getEdges();
            int[] textIndices = new int[edges.length];
            for (int i = 0; i < edges.length; i++) {
                textIndices[i] = getEdgeStringNumber(edges[i]);
            }
            StringBuilder stringBuilder = new StringBuilder();
            for (int textIndex : textIndices) {
                stringBuilder.append(textIndex);
                stringBuilder.append(',');
            }
            String key = stringBuilder.toString();
            CommonSubstring substring;
            if (longestSubstrings.containsKey(key)) {
                substring = longestSubstrings.get(key);
                if (substring.length >= status.height) {
                    continue;
                }
            } else {
                substring = new CommonSubstring();
                substring.textIndices = textIndices;
                longestSubstrings.put(key, substring);
                commonSubstrings.add(substring);
            }
            substring.length = status.height;
            int[] indices = new int[edges.length];
            for (int i = 0; i < edges.length; i++) {
                indices[i] = edges[i].beginIndex - status.height;
            }
            substring.beginIndices = indices;
        }
        return commonSubstrings;
    }

    private CommonSubstringStatus getLcsNodeStatus(Node node, int height, Map<Node, CommonSubstringStatus> statuses) {
        CommonSubstringStatus nodeStatus = new CommonSubstringStatus(node, height, _texts.length);
        if (node.getEdges().length == 0) {
            return nodeStatus;
        }

        for (Edge edge : node.getEdges()) {
            CommonSubstringStatus status = getLcsNodeStatus(edge.endNode,
                    height + getEdgeHeightForNodeStatus(edge), statuses);

            status.addString(getEdgeStringNumber(edge));
            nodeStatus.mergeStatus(status);
        }
        statuses.put(node, nodeStatus);
        return nodeStatus;
    }

}
